Papers with optimization problem
Augmenting Operations Research with Auto-Formulation of Optimization Models From Problem Descriptions (2022.emnlp-industry)
Copied to clipboard
Rindra Ramamonjison, Haley Li, Timothy Yu, Shiqi He, Vishnu Rengan, Amin Banitalebi-dehkordi, Zirui Zhou, Yong Zhang
| Challenge: | Existing systems for operations research use NLP to suggest formulations of optimization problems. |
| Approach: | They propose an augmented intelligence system that can be used to simplify and enhance the modeling experience for operations research. |
| Outcome: | The proposed system validates and edits the proposed formulations with a dataset of linear programming problems drawn from various application domains. |
Unsupervised Paraphrasing by Simulated Annealing (2020.acl-main)
Copied to clipboard
| Challenge: | Existing approaches to generate accurate and different-appearing paraphrases require massive parallel samples for training. |
| Approach: | They propose a novel approach that accomplishes Unsupervised Paraphrasing by Simulated Annealing by performing local editing. |
| Outcome: | The proposed approach outperforms existing models in automatic and human evaluations on Quora, Wikianswers, MSCOCO, and Twitter. |
Robustness Evaluation of Text Classification Models Using Mathematical Optimization and Its Application to Adversarial Training (2022.findings-aacl)
Copied to clipboard
| Challenge: | Neural networks are vulnerable to adversarial examples due to slightly perturbed input data. |
| Approach: | They propose a method that evaluates the robustness of text classification models by an optimization problem that identifies a minimum synonym swap that changes the classification result. |
| Outcome: | The proposed method achieves high scores in human evaluations of grammatical correctness and semantic similarity for an IMDb dataset and implements adversarial training with the IMD and SST2 datasets. |
Evaluating Readability and Faithfulness of Concept-based Explanations (2024.emnlp-main)
Copied to clipboard
| Challenge: | Existing methods for evaluating concepts from different perspectives lack a unified formalization. |
| Approach: | They propose a formal definition of concepts generalizing to diverse concept-based explanations’ settings and apply it to other types of explanations or tasks. |
| Outcome: | Extensive experimental analysis was carried out to determine the evaluation measures for explanation evaluation measures. |
A Formal Perspective on Byte-Pair Encoding (2023.findings-acl)
Copied to clipboard
| Challenge: | Byte-Pair Encoding (BPE) is a popular algorithm used for tokenizing data in NLP, but the underlying optimization problem that BPE seeks to solve has not yet been laid down. |
| Approach: | They propose an algorithm which is a 1/sigma*(1-e(-sigma))-approximation of an optimal merge sequence. |
| Outcome: | The proposed algorithm improves the runtime complexity from O(NM) to O(N log M) and the lower bound of the approximation is approx0.37. |
SwitchOut: an Efficient Data Augmentation Algorithm for Neural Machine Translation (D18-1)
Copied to clipboard
| Challenge: | Existing methods for data augmentation for text-based tasks such as machine translation are limited due to noise and noise. |
| Approach: | They propose a data augmentation policy with desirable properties as an optimization problem and propose 'SwitchOut' switchout randomly replaces words in both the source and target sentences with other random words from their corresponding vocabularies. |
| Outcome: | The proposed method outperforms strong alternatives such as word dropout on three translation datasets. |
WebInject: Prompt Injection Attack to Web Agents (2025.emnlp-main)
Copied to clipboard
| Challenge: | Despite advanced capabilities of MLLMs, prompt injection attacks remain vulnerable to emerging security and safety threats. |
| Approach: | They propose a prompt injection attack that manipulates webpage environment to induce web agent to perform attacker-specified action. |
| Outcome: | The proposed attack outperforms baselines on multiple datasets and is highly effective. |
Adapter Pruning using Tropical Characterization (2023.findings-emnlp)
Copied to clipboard
| Challenge: | Existing studies on adapter pruning have not examined the optimal number of adapter parameters needed for downstream applications. |
| Approach: | They propose an adapter pruning approach that prunes adapter parameters without changing the orientation of underlying tropical hypersurfaces. |
| Outcome: | The proposed approach prunes adapter layers without changing the orientation of underlying tropical hypersurfaces. |
BayesFlow: A Probability Inference Framework for Meta-Agent Assisted Workflow Generation (2026.findings-eacl)
Copied to clipboard
| Challenge: | Large Language Models (LLMs) have demonstrated remarkable generality, often solving tasks with a single carefully engineered prompt. |
| Approach: | They propose to cast automatic workflow generation as Bayesian inference over a posterior distribution on workflows and instantiate BayesFlow as Bayer-based workflow generation framework. |
| Outcome: | The proposed framework improves accuracy by 9 percentage points over baselines and 65 percentage points on pool-wide benchmarks. |
In-Context Example Ordering Guided by Label Distributions (2024.findings-naacl)
Copied to clipboard
| Challenge: | Prior work has shown that ICL is sensitive to different natural language instructions and different orderings of in-context examples. |
| Approach: | They propose two principles for in-context example ordering guided by model’s probability predictions. |
| Outcome: | The proposed model outperforms baseline models on 13 text classification datasets and nine autoregressive LLMs with 700M to 13B parameters. |
IMPACT: Importance-Aware Activation Space Reconstruction (2026.acl-long)
Copied to clipboard
| Challenge: | Large language models (LLMs) achieve strong performance across domains but remain difficult to deploy in resource-constrained environments due to their massive size. |
| Approach: | They propose an importance-aware activation reconstruction framework that links compression to its effect on model performance. |
| Outcome: | Experiments show that IMPACT reduces model size by 55.4% while maintaining accuracy comparable to or better than state-of-the-art models. |
Optimizing Decomposition for Optimal Claim Verification (2025.acl-long)
Copied to clipboard
| Challenge: | Existing decomposition and verification paradigms ignore their interactions and potential misalignment. |
| Approach: | They propose a reinforcement learning framework that leverages verifier feedback to learn a policy for dynamically decomposing claims to verifier-preferred atomicity. |
| Outcome: | The proposed framework outperforms existing decomposition policies in verification confidence tests . it improves accuracy and confidence by 0.12 on average across varying verifiers, datasets, and atomcities of input claims. |
Learning to Reason from Feedback at Test-Time (2025.acl-long)
Copied to clipboard
| Challenge: | Existing approaches to utilizing feedback are expensive and lack the time to perform iterative interactions with the environment. |
| Approach: | They propose a novel paradigm that formulates feedback utilization as an optimization problem at test time and a learnable test-time optimizer to effectively exploit feedback. |
| Outcome: | The proposed paradigm improves scalability and performance on two large language models across four reasoning datasets. |
Simple Algorithms For Sentiment Analysis On Sentiment Rich, Data Poor Domains. (C18-1)
Copied to clipboard
| Challenge: | Standard word embedding algorithms learn vector representations from large corpora of text documents in unsupervised fashion. |
| Approach: | They propose an algorithm that learns word embeddings jointly with a classifier . their algorithm leverages document label information to learn vector representations of words . |
| Outcome: | The proposed algorithm has superior performance on domains with limited data compared to other methods. |
Hybrid Preferences: Learning to Route Instances for Human vs. AI Feedback (2025.acl-long)
Copied to clipboard
Lester James Validad Miranda, Yizhong Wang, Yanai Elazar, Sachin Kumar, Valentina Pyatkin, Faeze Brahman, Noah A. Smith, Hannaneh Hajishirzi, Pradeep Dasigi
| Challenge: | Learning from human feedback has enabled the alignment of language models (LMs) with human preferences. |
| Approach: | They propose a Hybrid Preference routER that defers an annotation to either humans or LMs, achieving better annotation quality while reducing the cost of human-only annotation. |
| Outcome: | The proposed model achieves better annotation quality while reducing the cost of human-only annotation. |
Learning to Maximize Mutual Information for Chain-of-Thought Distillation (2024.findings-acl)
Copied to clipboard
| Challenge: | Knowledge distillation is a technique of transferring knowledge from large, complex models to smaller ones. |
| Approach: | They propose a method utilizing chain-of-thought distillation to transfer knowledge from large, complex models to smaller ones by maximizing mutual information of the representation features of the two tasks. |
| Outcome: | The proposed method outperforms the state-of-the-art knowledge distillation method on four datasets. |
B4: A Black-Box Scrubbing Attack on LLM Watermarks (2025.naacl-long)
Copied to clipboard
| Challenge: | Experimental results demonstrate superior performance of black-box scrubbing attack on watermarks compared with other baselines. |
| Approach: | They propose a black-box scrubbing attack on watermarks that embeds a hidden pattern invisible to human into generated content of a specific LLM. |
| Outcome: | The proposed method outperforms baselines in 12 different environments. |
VPTQ: Extreme Low-bit Vector Post-Training Quantization for Large Language Models (2024.emnlp-main)
Copied to clipboard
| Challenge: | Recent research has focused on pushing weight-only quantization to extremely low-bit due to numerical representation limitations. |
| Approach: | They propose a vector-based quantization approach that pushes LLMs to extremely low-bit . they propose scalar-based weight quantization that reduces memory requirements and optimizes storage costs . |
| Outcome: | The proposed method reduces model quantization perplexity by 0.01-0.34 on LLaMA-2, 0.38-0.68 on mistral-7B, 4.41-7.34, on llaMA-3 on QA tasks on average. |
Morfessor EM+Prune: Improved Subword Segmentation with Expectation Maximization and Pruning (2020.lrec-1)
Copied to clipboard
| Challenge: | Subword segmentation is a standard preprocessing step in many neural approaches to natural language processing. |
| Approach: | They propose to train a unigram subword model using a recursive algorithm and lexicon pruning algorithm. |
| Outcome: | The proposed method improves on the original training algorithm and improves morphological segmentation accuracy. |
Learning to Correct for QA Reasoning with Black-box LLMs (2024.emnlp-main)
Copied to clipboard
| Challenge: | Existing approaches to improve reasoning capability of large language models rely on accessibility or require significantly increased train- and inference-time costs. |
| Approach: | They propose a method to improve QA reasoning of large language models in a black-box setting by using a trained adaptation model to perform a seq2seq mapping from the often-imperfect reasonings of the original LLM to the correct or improved reasonings. |
| Outcome: | The proposed approach significantly improves reasoning accuracy across various QA benchmarks compared to the best-performing adaptation baselines. |
Pruning Pre-trained Language Models with Principled Importance and Self-regularization (2023.findings-acl)
Copied to clipboard
| Challenge: | Pre-trained language models often contain a vast amount of parameters, posing nontrivial requirements for storage and computation. |
| Approach: | They propose a pruning method where model prediction is regularized by the latest checkpoint with increasing sparsity throughout pruning. |
| Outcome: | The proposed approach is effective at sparsity levels, and can be applied to natural language understanding, question answering, and data-to-text generation tasks. |
Improving Unsupervised Keyphrase Extraction using Background Knowledge (L18-1)
Copied to clipboard
| Challenge: | Existing methods of keyphrase extraction are supervised and unsupervised . Topical PageRank uses topical information to extract the top topics of a document . |
| Approach: | They propose an unsupervised method for keyphrase extraction based on Wikipedia . they construct a semantic graph and transform the extraction problem into an optimization problem . |
| Outcome: | The proposed method improves over other state-of-the-art models by more than 2% in F1-score. |
Textual Data Augmentation for Efficient Active Learning on Tiny Datasets (2020.emnlp-main)
Copied to clipboard
| Challenge: | Existing active learning approaches for textual data are limited due to the complexity of language. |
| Approach: | They propose an approach where guided outputs of a language generation model can be enhanced through an active learning process. |
| Outcome: | The proposed approach achieves performance increases of 3% and 5% on TREC-6 and SST-2 datasets compared with NGDG, which does not optimize for a reward function. |
Efficient Data Labeling by Hierarchical Crowdsourcing with Large Language Models (2025.coling-main)
Copied to clipboard
| Challenge: | Large language models (LLMs) have been gaining attention for their impressive performance in in-context dialogues. |
| Approach: | They propose a hierarchical framework that leverages multiple LLMs for efficient data labeling under budget constraints. |
| Outcome: | The proposed framework outperforms human labelers and GPT-4 in terms of accuracy and efficiency. |
Accelerating Toeplitz Neural Network with Constant-time Inference Complexity (2023.emnlp-main)
Copied to clipboard
| Challenge: | Toeplitz Neural Networks outperform commonly used Transformer-based models while benefiting from log-linear space-time complexities. |
| Approach: | They propose to convert TNNs to SSMs during inference to combine strengths of TNN and SSM approaches. |
| Outcome: | The proposed method outperforms most Transformer-based models while retaining the advantage of constant inference complexity. |
CalibraEval: Calibrating Prediction Distribution to Mitigate Selection Bias in LLMs-as-Judges (2025.acl-long)
Copied to clipboard
| Challenge: | Empirical evaluations of large language models demonstrate that they improve performance in a wide range of tasks. |
| Approach: | They propose a label-free method for mitigating selection bias during inference by reformulating debiasing as an optimization task. |
| Outcome: | The proposed method mitigates selection bias and improves performance compared to existing methods. |
Chain-of-Thought Compression Should Not Be Blind: V-Skip for Efficient Multimodal Reasoning via Dual-Path Anchoring (2026.acl-long)
Copied to clipboard
| Challenge: | Existing efforts to mitigate this via token compression fail due to its autoregressive nature . linguistically redundant tokens are erroneously pruned, leading to hallucinations . |
| Approach: | They propose a method that reformulates token pruning as a Visual-Anchored Information Bottleneck (VA-IB) optimization problem. |
| Outcome: | Experiments on Qwen2-VL and Llama-3.2 families show that the proposed model achieves a speedup with negligible accuracy loss. |
LoRE-Merging: Exploring Low-Rank Estimation For Large Language Model Merging (2025.findings-emnlp)
Copied to clipboard
| Challenge: | a framework for model merging is proposed without additional training . task vectors from fine-tuned models exhibit a limited number of dominant singular values . |
| Approach: | They propose a framework for model merging based on low-rank estimation of task vectors without access to the base model. |
| Outcome: | The proposed framework improves models without additional training without additional inputs. |
Don’t Say No: Jailbreaking LLM by Suppressing Refusal (2025.findings-acl)
Copied to clipboard
| Challenge: | Large Language Models (LLMs) are vulnerable to "jailbreaking" attacks where crafted prompts manipulate them into producing toxic content. |
| Approach: | They propose to improve the target loss objective by combining a cosine decay schedule method with refusal suppression to achieve higher success rates. |
| Outcome: | The proposed approach outperforms baseline attacks and achieves state-of-the-art attack success rates. |
Learning Optimal Message Representations for Agentic Communication (2026.findings-acl)
Copied to clipboard
Shashwat Gupta, Anson Bastos, Mayukh Das, Supriyo Ghosh, Nagarajan Natarajan, Chetan Bansal, Saravan Rajmohan
| Challenge: | Existing approaches lack the intelligence necessary to understand, learn or apply optimal communication representations adaptively. |
| Approach: | They propose to dynamically learn the optimal message representations to enhance agentic performance by using an Expanding Markov Decision Process. |
| Outcome: | The proposed framework improves agentic performance while maintaining efficiency. |